package com.mlh.dp.背包问题.a01背包;

import java.util.Arrays;

/**
 * @author 缪林辉
 * @date 2024/4/18 11:50
 * @DESCRIPTION
 */
// 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
// 输入：nums = [1,5,11,5]
// 输出：true
// 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
public class 分割等和子集 {
    //方法一自己写出，利用暴力递归，不出意外超时了
    public boolean method1(int[] nums) {
        int total = 0;
        for (int i = 0; i < nums.length; i++) {
            total += nums[i];
        }
        if (total%2!=0){
            return false;
        }
       return process(nums,0,total/2,0);
    }

    public boolean process(int[] nums, int sum,int aim,int index) {
        if(sum==aim){
            return true;
        }else if(sum>aim){
            return false;
        }
        if(index>=nums.length){
            return false;
        }

        boolean b1 = process(nums, sum + nums[index], aim, index + 1);
        boolean b2=process(nums, sum, aim, index + 1);
        return b1||b2;
    }

    //方法二 去看了代码随想录中如何将这题转换成01背包问题的
    //然后自己写出代码
    public static boolean method2(int[] nums) {
        int total = 0;
        for (int i = 0; i < nums.length; i++) {
            total += nums[i];
        }
        if (total%2!=0){
            return false;
        }
        int target=total/2;
        int[]record=new int[target+1];
        for (int i = 0; i < nums.length; i++) {
            for (int j = target; j>=nums[i] ; j--) {
                record[j]=Math.max(record[j],record[j-nums[i]]+nums[i]);
            }
            if(record[target]==target){
                return true;
            }
        }
        return false;
    }

    //这转换成01背包问题的思路很牛逼
    public static boolean practice(int[] nums) {
        int sum=0;
        for (int temp : nums) {
            sum+=temp;
        }
        if(sum%2!=0){
            return false;
        }
        sum=sum/2;
        int len=nums.length;
        int[]dp=new int[sum+1];
        //初始化
        for (int i = nums[0]; i < sum; i++) {
            dp[i]=nums[0];
        }
        for (int i = 1; i < len; i++) {
            for (int j = sum; j >=nums[i]; j--) {
                dp[j]=Math.max(dp[j-nums[i]]+nums[i],dp[j]);
            }
        }
        if(dp[sum]==sum){
            return true;
        }
        return false;
    }

    //书包容量（重量）最大的为total/2的情况下，能装下多重的东西，最大就是刚好装满，也就是我们需要的结果
    //在思考过程中一定要理解数组的含义，带几个具体的数值进去思考（尤其是边界条件）
    public boolean practice2(int[] nums) {
        int total=0;
        for (int i = 0; i < nums.length; i++) {
            total+=nums[i];
        }
        if(total%2!=0){
            return false;
        }
        int[]dp=new int[total/2+1];
        for (int i = 0; i < nums.length; i++) {
            for (int j = total/2; j >=nums[i] ; j--) {
                dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        if(dp[total/2]==total/2){
            return true;
        }
        return false;
    }

}
